package work;

/**
 * @author hy
 */
public class MaxHeap<T extends Comparable<T>> {
    private int size;
    private int count;
    private T[] heap;

    public MaxHeap(int size) {
        heap = (T[]) new Comparable[size];
        this.size = size;
        count = 0;
    }

    public void add(T value) {
        if (count == 0) {
            heap[count] = value;
        } else {
            heap[count] = value;
            int current = count;
            int par = (current - 1) / 2;
            while (true) {
                if (heap[par].compareTo(heap[current]) < 0) {
                    replace(par, current);
                    current = par;
                    par = (current - 1) / 2;
                } else {
                    break;
                }
            }
        }
        count++;
        if (count == size) {
            T[] array = (T[]) new Comparable[size * 2];
            System.arraycopy(heap, 0, array, 0, size);
            heap = array;
            size *= 2;
        }
    }

    public void delete() {
        heap[0] = heap[--count];
        heap[count] = null;
        int current = 0;
        int left = current * 2 + 1;
        int right = current * 2 + 2;
        while (true) {
            if (heap[left] != null && heap[right] != null && heap[current].compareTo(heap[left]) < 0 && heap[current].compareTo(heap[right]) < 0) {
                if (heap[left].compareTo(heap[right]) < 0 || heap[left].compareTo(heap[right]) == 0) {
                    replace(right, current);
                    current = left;
                } else {
                    replace(left, current);
                    current = right;
                }
                left = current * 2 + 1;
                right = current * 2 + 2;

            } else if (heap[left] != null && heap[current].compareTo(heap[left]) < 0) {
                replace(left, current);
                current = left;
                left = current * 2 + 1;
                right = current * 2 + 2;
            } else if (heap[right] != null && heap[current].compareTo(heap[right]) < 0) {
                replace(right, current);
                current = right;
                left = current * 2 + 1;
                right = current * 2 + 2;
            } else {
                break;
            }
        }
    }

    public void printf() {
        for (T value : heap) {
            if (value == null) {
                break;
            }
            System.out.print(value + " ");
        }
    }

    private void replace(int initial, int target) {
        T value;
        value = heap[initial];
        heap[initial] = heap[target];
        heap[target] = value;
    }

}
